package com.leetcode.partition2;

import java.util.Arrays;

/**
 * @author `RKC`
 * @date 2021/9/3 21:56
 */
public class LC135分发糖果 {

    public static int candy(int[] ratings) {
        return greedy(ratings);
    }

    public static void main(String[] args) {
        int[] ratings = {1, 2, 2};
        System.out.println(candy(ratings));
    }

    private static int greedy(int[] ratings) {
        int[] candyVec = new int[ratings.length];
        candyVec[0] = 1;
        //从前向后遍历，局部最优：只要右边评分大于左边评分，右边孩子就多一个糖果。全局最优：相邻的孩子，评分高的右孩子获得的糖果比左孩子多
        for (int i = 1; i < ratings.length; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candyVec[i] = candyVec[i - 1] + 1;
            } else {
                candyVec[i] = 1;        //保证每个小孩至少能分得一个糖果
            }
        }
        // 从后往前遍历，如果ratings[i] > ratings[i + 1]，此时candyVec[i]就有两个选择，一是candyVec[i + 1] + 1，
        // 另一个是candyVec[i]（之前比较右孩子大于左孩子的糖果数量），局部最优：candyVec[i] = Math.max(candyVec[i], candyVec[i + 1] + 1)，
        // 保证i孩子的糖果数量大于左边也大于右边。全局最优：相邻的孩子，评分高的孩子获得更多的糖果
        for (int i = ratings.length - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                candyVec[i] = Math.max(candyVec[i], candyVec[i + 1] + 1);
            }
        }
        int answer = 0;
        for (int i : candyVec) answer += i;
        System.out.println(Arrays.toString(candyVec));
        return answer;
    }
}
